1. Field Of The Invention
The present invention relates to the imaging arts, and more particularly, to range imaging employing parallax.
2. Description Of Prior Art
The use of robots in industry is becoming more and more common. Most of the robot applications are limited to simple tasks such as spray painting, welding and material handling. A broader range of applications will depend on technological developments in several areas, one of which is the improved performance of visual sensors.
The technology for building robots has been available for at least two decades. The mechanics of moving a suitable manipulator through three dimensional space is well known technology in which improvements are incremental and evolutionary. The developments in robots have been paced by the application of electric/electronic control technology to the industrial environment. The first robots were simple and not easily reprogrammable. With the advent of microprocessors and the lead of Japanese robotics, American manufacturers have been compelled to use robots to improve productivity.
Many of the robots available today are targeted for simple, restrictive tasks which require repetitive non-adaptive control. The typical installation incurs a hidden cost which is larger than the unit cost of the robot itself because of the special peripheral jigging required to support the robot. A reliable, easy to use vision system which endows the robot with more flexibility in coping with a human-like environment would eliminate these additional system costs. Such a system would also broaden the application of robots into more complex operations such as assembly which constitutes a far larger percentage of tasks in American factories than welding and spray painting.
Robot vision is an old problem which has been attacked by trying to imitate the human visual process. While steady progress has been made, it has been slow and requires a basic theoretical breakthrough before vision reaches its full potential in robotics. The current state-of-the-art is just entering real-time gray scale processing for robots and has been only marginally useful in military reconnaissance and industry.
One symptom of the present difficulties in robot vision is that most applications require special development such as tailored lighting and custom computer software. System costs are often high and response times are slow. While some companies are promising general vision capability, a little exploration reveals improved processing capabilities in two-dimensional imaging limited by the same fundamental problems.
For instance, imagine a robot staring into a barrel of parts which have various maskings, labels, shadows and contours. The first step in currently available vision processors is to partition the image into regions of "sameness" or "blobs". The definition of "sameness" might be based upon intensity, color or texture in conventional image processing, but the result upon real images is generally the same--confusion! An image is broken up into many regions of highlights, shadows and contours which are useless to the robot without further processing. Even a human often has difficulty recognizing a scene from this first level partitioning.
Not only is the image partitioning difficult to use, but it is very expensive and slow to produce. Simple level slicing or binary imaging is pointless, except when special lighting and background can be used. Thus, serial processing is generally required, involving complex logic and creating a severe bottleneck.
To overcome the problems inherent with intensity imaging or the like, range imaging has been employed. Time-of-flight systems employ a difference in phase between reflected light and reference light to determine the length of time for transmitted light to be reflected back as an indication of range. Such systems are described in U.S. Pat. No. 3,945,729 to Rosen, Duda et al "Use Of Range And Reflectance Date To Find Planar Surface Regions", IEEE Transactions On Pattern Analysis And Machine Intelligence, Vol. PAMI-1, No. 3 July 1979, and Nitzan et al, "The Measurement And Use Of Registered Reflectance And Range Data In Scene Analysis", Proceedings Of The IEEE, Vol. 65, No. 2 February 1977. Such systems are inadequate for robot control, since scanning systems are too slow as well as generally inaccurate and without sufficient resolution.
Range imaging may also be conducted employing parallax. Stereo correlation systems and scanning sheet of light systems may both be considered parallax systems. Stereo correlation is slow because of its software processing load and low resolution, since it must match many pixels to get one range measurement. It also requires object structure to make the range measurement which is a major weakness for a robot sensor which is required to manipulate unmarked objects.
Range sensors, based on the sheet of light technique are described in Nevatia et al, "Structured Descriptions Of Complex Objects", Proc. 3rd Int. Joint Conf. Artificial Intelligence, August 1973 and Shirai et al, "Recognition Of Polyhedrons With A Range Finder", Proc. 2nd Int. Joint Conf. Artificial Intelligence, September 1971. In theory, sheet of light systems can be made fast, but in practice they are slow. To achieve a narrow, scanning sheet of light a few meters away requires a laser beam which is either limited to a few milliwatts or is extraordinarily expensive. The low power illumination forces a slow scan rate to achieve an adequate signal-to-noise ratio. The sensor must measure the time at which each pixel is illuminated, and this time is directly translatable into pixel range. This measurement is slow, since a full frame is required for each position of the laser beam illumination line. One could conceive of having more than one illumination line appear on each frame to speed up the process, but one would still have to repeat the scan many times in synchronization with the TV camera to cover the entire image.
Rocker et al in "Methods For Analyzing Three Dimensional Scenes", Proc. 4th Int. Joint Conf. Artificial Intelligence, September 1975, suggests employing an optical grid projected onto a scene to be imaged. However, this article suggests that processing can be done by tracing the images of the intersecting lines in the picture. Computation of three-dimensional coordinates can be done only if it is possible to identify the images of the lines by their mathematical equations. The article indicates that it takes the computer about thirty seconds to determine the complete three-dimensional coordinates of the lines. In many applications, including robotics, this period of time may be excessively long.